package com.k.kc.util.tree.demo2;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * 树构建支持多根节点
 *
 * @param <T> 类型
 */
public class TreeUtil<T extends BaseTreeNode> {

    private final List<T> treeList;
    Map<String,BaseTreeNode> treeMap;

    public TreeUtil(List<T> list) {
        this.treeList = list;
    }

    private boolean existParent(T a) {
        if (a.getParentKey().equals(a.getKey())) {
            return false;
        }
        if(treeMap!=null){
            return treeMap.get(a.getParentKey())!=null;
        }
        for (T t : treeList) {
            if (t.getKey().equals(a.getParentKey())) {
                return true;
            }
        }
        return false;
    }
    private boolean existChildren(T node){
        for (T t : treeList) {
            if(t.getKey().equals(t.getParentKey())){
                continue;
            }
            if(t.getParentKey().equals(node.getKey())){
                return true;
            }
        }
        return false;
    }

    private List<T> findRootList(List<T> t) {
        // root sort
        return t.stream().filter(a ->
                !existParent(a)
        ).sorted(Comparator.comparingInt(T::getSort))
                .peek(b->b.setLeaf(true))
                .collect(Collectors.toList());
    }

    private void fillChildren(List<T> listRoot, List<T> listAll) {
        for (T root : listRoot) {
            fillChildrenOne(root, listAll);
        }
    }

    private void fillChildrenOne(T t, List<T> listAll) {
        for (T itm : listAll) {
            // root
            if (itm.getKey().equals(itm.getParentKey())) {
                continue;
            }
            if (t.getKey().equals(itm.getParentKey())) {
                t.setLeaf(false);
                t.getChildren().add(itm);
                fillChildrenOne(itm, listAll);
            }else{
                t.setLeaf(true);
            }
            // children sort
            t.getChildren().sort(Comparator.comparingInt(BaseTreeNode::getSort));
        }
    }

    public List<T> build() {
        if (treeList == null || treeList.isEmpty()) {
            throw new IllegalArgumentException("argument error");
        }
        // key 重复会抛出异常
        treeMap = treeList.parallelStream().collect(Collectors.toMap(T::getKey, n -> n));
        if(treeMap.size()>0){
            List<T> rootList = findRootList(treeList);
            fillChildren(rootList, treeList);
            return rootList;
        }
        return Collections.emptyList();
    }
}
